﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/find-target-indices-after-sorting-array/
/*
题目描述：
给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。
目标下标 是一个满足 nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。
返回的列表必须按 递增 顺序排列。

示例 1：
输入：nums = [1,2,5,2,3], target = 2
输出：[1,2]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 2 的下标是 1 和 2 。

示例 2：
输入：nums = [1,2,5,2,3], target = 3
输出：[3]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 3 的下标是 3 。

示例 3：
输入：nums = [1,2,5,2,3], target = 5
输出：[4]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 5 的下标是 4 。

示例 4：
输入：nums = [1,2,5,2,3], target = 4
输出：[]
解释：nums 中不含值为 4 的元素。
 
提示：
1 <= nums.length <= 100
1 <= nums[i], target <= 100
*/

// 方法1——直接遍历
/*
思路：
在对数组进行非降序排序后，直接遍历数组，如果遇到nums[i] == target
则将i写入answer数组。
如此一直往后遍历，answer数组也往后一直写入，最后返回answer数组即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整型的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
int* targetIndices1(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	// 先对数组进行排序
	qsort(nums, numsSize, sizeof(int), cmp_int);
	int* answer = (int*)malloc(numsSize * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	int n = 0;
	int i = 0;
	for (i = 0; i < numsSize; i++) {
		if (nums[i] == target) {
			answer[n] = i;
			n++;
		}
	}
	*returnSize = n;
	return answer;
}
// 时间复杂度O(nlogn)，n为数组长度，时间复杂度主要取决于排序数组的复杂度。
// 空间复杂度：O(n)，n为数组长度，最坏情况下，我们需要n个额外空间来存储返回列表。

// 方法2——二分查找
/*
思路：
在对数组进行非降序排序后，我们可以使用二分查找法来找到第一个target的元的下标first和第一个大于target的元素的下标last，
将这两个下标相减，其结果n就是数组中target的个数，然后循环n次在answer中写入
first到first + n - 1即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个二分查找法
int binary_search(int left, int right, int* nums, double target) {
	assert(nums);
	int mid = 0;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return left;
}
int* targetIndices2(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	// 先对数组进行排序
	qsort(nums, numsSize, sizeof(int), cmp_int);
	int* answer = (int*)malloc(numsSize * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	int first = binary_search(0, numsSize - 1, nums, target - 0.5); // 寻找target - 0.5其实返回的是第一个target的下标
	int last = binary_search(first, numsSize - 1, nums, target + 0.5); // 寻找target + 0.5其实返回的是target + 0.5应该被顺序插入的坐标，也就是第一个大于target的元素的坐标
	int n = last - first;
	int i = 0;
	for (i = 0; i < n; i++) {
		answer[i] = first + i;
	}
	*returnSize = n;
	return answer;
}
// 时间复杂度：O(nlogn)，n为数组的长度，对数组进行排序的复杂度为nlogn，二分查找的复杂度为logn，故总的时间复杂度为nlogn。
// 空间复杂度：O(n)，n为数组的长度，最坏情况下，我们需要n个额外空间来存储返回元素。


